<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>排序算法</title>
</head>

<body>
    <script>
        main();
        function main() {
            let array = [7, 3, 1, 9, 0, 4, 2];
            quickSort(array);
            console.log(array);
        };
        // 冒泡排序
        function booble(array) {
            for (let i = 0; i < array.length; i++) {
                for (let j = 0; j < array.length - i - 1; j++) {
                    if (array[j] > array[j + 1]) {
                        let now = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = now;
                    }
                }
            }
            return array;
        }
        // 改进后-冒泡排序
        function booble2(array) {
            for (let i = 0; i < array.length; i++) {
                let flag = false;
                for (let j = 0; j < array.length - i - 1; j++) {
                    if (array[j] > array[j + 1]) {
                        let now = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = now;
                        flag = true
                    }
                }
                if (!flag) {
                    return array
                }
            }
            return array;
        }
        // 快速排序
        /**
         * 找一个基准，小的放左，大的放右；分别对左右两部分进行递归操作
        */
        /*
        时间复杂度：
        理想：nlogn；最差：n^2(退化为冒泡排序)
        空间复杂度：
        理想：logn(就地快排空间使用是O(1)，主要是递归调用消耗空间，因为每次递归都要保留一些数据)；最差：n(退化为冒泡排序)


        */
        function quickSort(array) {
            _quickSort(array, 0, array.length - 1);
        }
        function _quickSort(array, l, r) {
            if (l >= r) return;
            let p = partition(array, l, r);
            _quickSort(array, l, p - 1);
            _quickSort(array, p + 1, r);
        }
        function partition(array, l, r) {
            let j = l;
            for (let i = l + 1; i <= r; i++) {
                if (array[i] < array[l]) {
                    swap(array, j + 1, i);
                    j++;
                }
            }
            swap(array, l, j);
            return j;
        }
        function swap(array, l, r) {
            let now = array[l];
            array[l] = array[r];
            array[r] = now;
        }
    </script>

</body>

</html>